LeetCode 102、二叉树的层序遍历

一、题目描述

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉树的层序遍历（ LeetCode 102 ）:https://leetcode-cn.com/problems/binary-tree-level-order-traversal
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        // 设置 res 用来保存输出结果
        List<List<Integer>> res = new LinkedList<>();
        // 边界情况处理
        if(root == null) return res;
        
        // 设置一个队列，用来存储二叉树中的元素
        Queue<TreeNode> queue = new LinkedList<>();
        // 队列添加二叉树的根节点
        queue.add(root);

        // 遍历队列，直到队列为空，说明访问了二叉树中所有的节点
        while(!queue.isEmpty()){  
            // 用来记录 queue 的长度，即每层节点的个数
            int size = queue.size();  

            // 用来保存每一层节点，保存成功后添加到 res 中
            List<Integer> temp =  new ArrayList<>(); 
  
            // 使用 for 循环，将 queue 中的元素添加的 temp 中
            for(int i = 0 ; i < size ;  i++ ){     
                // 从 queue 中取出一个节点         
                TreeNode node = queue.poll();  
                // 把节点存放到 list 中
                temp.add(node.val);  //将节点值加入list

                // 判断当前节点的左子节点是否有值，如果有，则添加到 queue 中
                if(node.left != null)
                    queue.add(node.left);

                // 判断当前节点的右子节点是否有值，如果有，则添加到 queue 中    
                if(node.right != null)
                    queue.add(node.right);
            }

            // 把存放了每一层元素的数组 temp 添加到 res 中
            res.add(temp);
        }

        // 返回 res
        return res; 
    }
}

**2、**C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉树的层序遍历（ LeetCode 102 ）:https://leetcode-cn.com/problems/binary-tree-level-order-traversal
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        // 设置 res 用来保存输出结果    
        vector<vector<int>> res;
        // 边界情况处理
        if(root == NULL) return res;

        // 设置一个队列，用来存储二叉树中的元素
        queue<TreeNode*> myqueue;
        // 队列添加二叉树的根节点
        myqueue.push(root);

        // 遍历队列，直到队列为空，说明访问了二叉树中所有的节点
        while(!myqueue.empty()){  
            // 用来记录 myqueue 的长度，即每层节点的个数
            int size = myqueue.size();  

            // 用来保存每一层节点，保存成功后添加到 res 中
            vector<int> temp;

            // 使用 for 循环，将 myqueue 中的元素添加的 temp 中
            for(int i = 0 ; i < size ;  i++ ){     
                // 从 myqueue 中取出一个节点         
                TreeNode* node = myqueue.front();
    myqueue.pop();    
                // 把节点存放到 list 中
                temp.push_back(node->val);  //将节点值加入list

                // 判断当前节点的左子节点是否有值，如果有，则添加到 myqueue 中
                if(node->left != NULL)
                    myqueue.push(node->left);

                // 判断当前节点的右子节点是否有值，如果有，则添加到 myqueue 中    
                if(node->right != NULL)
                    myqueue.push(node->right);
            }

            // 把存放了每一层元素的数组 temp 添加到 res 中
            res.push_back(temp);
        }

        // 返回 res
        return res; 
    }
};

3、Python 代码

#登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 二叉树的层序遍历（ LeetCode 102 ）:https://leetcode-cn.com/problems/binary-tree-level-order-traversal
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:

        # 设置 res 用来保存输出结果
        res = []

        # 边界情况处理
        if not root :
           return res
        
        # 设置一个队列，用来存储二叉树中的元素
        queue = deque()
        
        # 队列添加二叉树的根节点
        queue.append(root)

        # 遍历队列，直到队列为空，说明访问了二叉树中所有的节点
        while queue :
            # 用来记录 queue 的长度，即每层节点的个数
            size = len(queue)

            # 用来保存每一层节点，保存成功后添加到 res 中
            temp = []
        
            # 使用 for 循环，将 queue 中的元素添加的 temp 中
            for _ in range(size) :
                # 从 queue 中取出一个节点         
                node =  queue.popleft()
                # 把节点存放到 list 中
                temp.append(node.val)

                # 判断当前节点的左子节点是否有值，如果有，则添加到 queue 中
                if node.left : queue.append(node.left)
                   

                # 判断当前节点的右子节点是否有值，如果有，则添加到 queue 中    
                if node.right : queue.append(node.right)
                    

            # 把存放了每一层元素的数组 temp 添加到 res 中
            res.append(temp)
        

        # 返回 res
        return res